import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:506：相对名次、148：排序链表 27：移除元素
 * Date: 2024-02-07
 * Time:22:41
 */
public class Solution {
    public static String[] findRelativeRanks(int[] score) {
        int len = score.length;
        String[] ret = new String[len];
        //List<String> list = new ArrayList<>();
        PriorityQueue<Integer> q = new PriorityQueue<>(len);
        for(int s : score) {
            q.offer(s);
        }
        int rank = len;
        //处理第四名开始及之后的
        while(rank > 0) {
            //取出q中分数最低的，遍历原数组找出它的下标，置为len
            int poll = q.poll();
            int index = findVal(score,poll);
            if(rank > 3) {
                String str = String.valueOf(rank);
                ret[index] = str;
            } else {
                if(rank == 1) {
                    ret[index] = "Gold Medal";
                }
                if(rank == 2) {
                    ret[index] = "Silver Medal";
                }
                if(rank == 3) {
                    ret[index] = "Bronze Medal";
                }

            }
            --rank;
        }
        return ret;

    }

    private static int findVal(int[] score,int val) {
        for(int i = 0;i<score.length;i++) {
            if(score[i] == val)
                return i;
        }
        return -1;
    }
///////////////////////////////////////////////////////////
    //排序链表

    public ListNode sortList(ListNode head) {
        if(head == null)
            return new ListNode();
        return null;
    }
///////////////////////////////////////////////////////////
    //移除元素
    public static int removeElement(int[] nums, int val) {
        //遇到等于val的元素，就往后找不等于val的a，然后让a把那个元素给覆盖掉
        //遇到某个数字val，就标记出来
        int len = nums.length;
        if(len == 0)
            return 0;
        int left = 0,right = len-1;  //双指针
        int count = 0;  //计数器，每移除一个元素count就加1，最终新数组长度就是len-count
        while(left < right) {
            while(left < len && left < right && nums[left] != val) {
                ++left;
            }
            //此时left指向的元素为val
            while(right >= 0 && left < right && nums[right] ==val) {
                --right;
            }

            nums[left] = nums[right];
            ++left;
            --right;
            ++count;
        }
/*
        while(quick < len) {
            //让slow和fast停在val处
            while(slow < len && quick < len && nums[slow] != val) {
                ++slow;
                if(quick <= slow)
                    ++quick;
            }

            //quick继续走，直到遇到某个不是val的元素，然后让它把那个元素给覆盖掉
            while(quick < len && nums[quick] == val) {
                ++quick;
            }
            nums[slow++] = nums[quick++];
            ++count;
        }
*/
        return len-count-1;

    }

    private static void swap(int a,int b) {
        int tmp = a;
        a = b;
        b = tmp;
    }

}
